Systems that use dynamically generated secrets (e.g., one-time passcodes) as part of an authentication process often employ multiple authenticating functions (e.g., authentication servers) to increase the efficiency of the system. For example:                Multiple authenticating functions improve scaling performance by increasing the availability of authentication services at peak access times.        Multiple authenticating functions reduce authentication burden required for any single authentication function. Typical size constraints of cryptographic databases limit the number of authentications a single authenticating function can perform per unit time.        Multiple authenticating functions also allow wider geographic use. Users that are geographically remote from an authenticating function may incur unacceptable authentication delays or timeouts due to communication latency between the user and the authenticating function. Having geographically distributed authenticating functions solves this problem.        
Systems with multiple authenticating functions are vulnerable to “replay” attacks. In a replay attack, an attacker intercepts and records a one-time passcode (OTP) that a legitimate user provides to an authenticating function. The attacker then replays the intercepted one-time passcode to a different authenticating function in the network in order to procure an unauthorized authentication.
One way to mitigate such replay attacks is to keep track of the “high water mark” (HWM) associated with each token or other function (hereinafter ‘token’) that generates a one-time passcode. During an authentication, there is information that needs to be known to all instances of the authenticating function in order to prevent a reply attack. For example, in the case of a time-based OTP token, the time of the last successful authentication would be the HWM, and is used to assure that any future authentication requests are accepted only if the time associated with that authentication request is after the HWM. In another example, in the case of a counter-based OTP token, the counter value of the last successful authentication would be the HWM. The HWM of a time-based token is a value that identifies the most recent time of authentication associated with a particular one-time passcode generated by that time-based token.
In many cases, the HWM is simply the last login time for the token. Each time that a time-based token submits a one-time passcode to an authenticating function (i.e., the current login time), the authenticating function evaluates the HWM for that token, to determine if the passcode has already been used to authenticate through a different authenticating function. If the current login time is equal to or earlier than the HWM that token, the authenticating function denies authentication for that passcode. The current login time being earlier than the HWM indicates that the passcode has already been used.
For counter-based tokens, all authenticating functions in the network must similarly be aware of the current count for all counter-based tokens. The HWM in this case tracks the counter value for the latest successful authentication. By using the HWM it can be assured that no authentication codes associated with a counter value equal to or less than the HWM are allowed.
A problem with using the HWM concept described above to thwart replay attacks is how to disseminate the HWM information for all tokens in the system to all authenticating functions in the system. One prior art system uses a “flooding” technique, which entails propagating the HWM associated with a token to all authenticating functions in the system whenever the HWM for that token changes. This technique works adequately when the number of tokens in the system is relatively small, but becomes more unwieldy as the number of tokens increases. Thus using the flooding technique to disseminate HWM information adversely affects the ability to scale the system from a performance point of view. Further, the flooding technique makes it difficult to be certain all authenticating functions in the system have the most up-to-date HWM information.